package hwOne4;

import edu.princeton.cs.algs4.StdDraw;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.Stopwatch;

public class DoublingTest {

    // 模拟的实验：计算随机数对的 TwoSum 数量
    public static double timeTrial(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = StdRandom.uniform(-1000000, 1000000);
        }
        Stopwatch timer = new Stopwatch();
        int count = countTwoSum(a); // 使用 TwoSum 暴力求解
        return timer.elapsedTime();
    }

    // 暴力求解 TwoSum 的实现
    public static int countTwoSum(int[] a) {
        int n = a.length;
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (a[i] + a[j] == 0) count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        // 设置画布比例
        StdDraw.setCanvasSize(800, 600);
        StdDraw.setXscale(0, 10); // X轴初始比例
        StdDraw.setYscale(0, 10); // Y轴初始比例
        StdDraw.setPenRadius(0.005);

        // 初始化变量
        int maxTrials = 200; // 最大实验次数
        double[] x = new double[maxTrials]; // 存储 X 坐标（log(N)）
        double[] y = new double[maxTrials]; // 存储 Y 坐标（log(T) 或 T）

        for (int i = 0; i < maxTrials; i++) {
            int n = (int) Math.pow(2, i + 1); // 输入规模倍增
            double time = timeTrial(n); // 测试运行时间

            // 处理运行时间为 0 的情况
            if (time <= 0) {
                time = 1; // 设置为最小正值，避免 log(0)
            }

            // 标准图像的点
            StdDraw.setPenColor(StdDraw.BLACK);
            StdDraw.point(i + 1, time); // 标准图像的时间（线性比例）

            // 对数图像的点
            double logX = Math.log(n) / Math.log(2); // log(N)
            double logY = Math.log(time) / Math.log(2); // log(T)
            x[i] = logX;
            y[i] = logY;

            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.point(logX, logY); // 对数图像的点
        }

        // 调整比例以使图像充满窗口
        StdDraw.setPenColor(StdDraw.BLUE);
        StdDraw.setXscale(0, x[maxTrials - 1] + 1); // 调整 X 轴（对数图像）
        StdDraw.setYscale(0, y[maxTrials - 1] + 1); // 调整 Y 轴（对数图像）
        for (int i = 0; i < maxTrials; i++) {
            StdDraw.setPenColor(StdDraw.RED);
            StdDraw.point(x[i], y[i]); // 再绘制对数图像的点
        }
    }
}